import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/23 15:24
 * @description 字符串哈希，首先分析下界，最少需要多少复制次数，那么 ss 的长度肯定要大于 b的长度，b才会有可能成为ss的子串
 * 上界，最多需要复制多少次，由于主串是由a复制而来，并且是在主串中ss中找到 b, 那么b的起始位置，不会超过a的长度。
 * 长度越过 a 长度的起始匹配位置，必然在此前已经被匹配过了。
 * 因此假设 下界复制 c1次，上界复制 c1 + 1次，
 */
public class Solution2 {
    public static void main(String[] args) {

    }

    public int repeatedStringMatch(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int ans = 0;
        // 下界复制次数
        while (sb.length() < b.length() && ++ans > 0) {
            sb.append(a);
        }
        // 上界复制次数
        sb.append(a);
        // 哈希值相同的下标位置初始位置
        int idx = strHash(sb.toString(), b);
        if (idx == -1) {
            return -1;
        }
        // 如果匹配成功后的结束位置不超过了 n * c1，说明复制 c1 即可，返回 c1，超过则返回 c2；匹配不成功则返回 -1。
        return idx + b.length() > a.length() * ans ? ans + 1 : ans;
    }
    public int strHash(String ss, String b) {
        int P = 131;
        int n = ss.length(), m = b.length();
        // 将b附加到最后，那么[len-m+1, len]这部分就是b串的哈希值
        String str = ss + b;
        int len = str.length();
        int[] h = new int[len + 10], p = new int[len + 10];
        p[0] = 1;
        for (int i = 0; i < len; i++) {
            p[i + 1] = p[i] * P;
            h[i + 1] = h[i] * P + str.charAt(i);
        }
        int r = len, l = r - m + 1;
        // b 的哈希值
        int target = h[r] - h[l - 1] * p[r - l + 1];
        for (int i = 1; i <= n; i++) {
            int j = i + m - 1;
            // 子串哈希值
            int cur = h[j] - h[i - 1] * p[j - i + 1];
            if (cur == target) {
                return i - 1;
            }
        }
        return -1;
    }
}
